"""
@author: 景云鹏
@email: 310491287@qq.com
@date: 2022/6/13
"""
from functools import lru_cache


class Solution:
    def __init__(self):
        self.dp = None
        self.s = None
        self.regs = []

    def isMatch(self, s: str, p: str) -> bool:
        i = 0
        while i < len(p) - 1:
            if p[i + 1] != '*':
                self.regs.append(p[i])
                i += 1
            else:
                self.regs.append('{}*'.format(p[i]))
                i += 2
        if not p.endswith('*'):
            self.regs.append(p[-1])

        self.dp = [[-1] * len(s) for _ in range(len(self.regs))]
        self.s = s
        return self.cal(0, 0)

    @lru_cache
    def cal(self, i, j):
        if i == len(self.regs):
            return j == len(self.s)
        while '*' not in self.regs[i]:
            if self.regs[i] != '.' and self.regs[i] != self.s[j]:
                return False
            i += 1
            j += 1
            if i == len(self.regs):
                return j == len(self.s)
            if j == len(self.s):
                for reg in self.regs[i:]:
                    if not reg.endswith('*'):
                        return False
                else:
                    return True
        c = self.regs[i][0]
        while j < len(self.s):
            if c != '.' and c != self.s[j]:
                return self.cal(i + 1, j)

            if i == len(self.regs) - 1:
                if c == '.':
                    return True
                if len(set(self.s[j:])) == 1 and self.s[j] == c:
                    return True

            if self.cal(i + 1, j):
                return True
            j += 1
        else:
            return all(len(_) == 2 for _ in self.regs[i:])


if __name__ == '__main__':
    "abbaaaabaabbcba"
    "a*.*ba.*c*..a*.a*."
    sol = Solution()
    tests = {
        'a': 'a',
        'abaa': 'a*ba*',
        'ab': '.*',
        "aa": "a.*c*",
        "aba": "a*.a*."
    }
    for st, p in tests.items():
        if not sol.isMatch(st, p):
            print(st, p)
            sol = Solution()
            sol.isMatch(st, p)
